/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        130b.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/17 17:44
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
#include "../header.h"

class UF {
public:
    explicit UF(int n) : parent(n), size(n, 1), count(n) {
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    /* 将 p 和 q 连接 */
    void Union(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return;
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        } else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }

    /* 判断 p 和 q 是否连通 */
    bool Connected(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return true;
        return false;
    }

    /* 返回图中有多少个连通分量 */
    int Count() {
        return count;
    }

private:
    vector<int> parent;
    vector<int> size; // size[i] i的节点数
    int count;

    int find(int p) {
        while (parent[p] != p) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
};

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        int n = board.size();
        if (n == 0)
            return;
        int m = board[0].size();
        UF uf(m * n + 1); // [0, m * n - 1]
        int dummy = m * n;
        for (int i = 0; i < n; ++i) {
            if (board[i][0] == 'O')
                uf.Union(i * m, dummy);
            if (board[i][m - 1] == 'O')
                uf.Union(i * m + m - 1, dummy);
        }
        for (int i = 1; i < m - 1; ++i) {
            if (board[0][i] == 'O')
                uf.Union(i, dummy);
            if (board[n - 1][i] == 'O')
                uf.Union(m * n - m + i, dummy);
        }
        vector<vector<int>> d = {{1,  0},
                                 {0,  1},
                                 {-1, 0},
                                 {0,  -1}};
        for (int i = 1; i < n - 1; ++i) {
            for (int j = 1; j < m - 1; ++j) {
                if (board[i][j] == 'O')
                    for (int k = 0; k < 4; ++k) {
                        int x = i + d[k][0];
                        int y = j + d[k][1];
                        if (board[x][y] == 'O')
                            uf.Union(x * m + y, i * m + j);
                    }
            }
        }
        for (int i = 1; i < n - 1; ++i) {
            for (int j = 1; j < m - 1; ++j) {
                if (board[i][j] == 'O' && !uf.Connected(i * m + j,dummy))
                    board[i][j] = 'X';
            }
        }
    }
};


